package leetcode.od;

import org.junit.Test;

import java.util.*;

/**
 * @author pppppp
 * @date 2022/3/11 10:37
 * <p>
 * 题目1：叠积木
 * 给出一个列表如[[6,7,],[5,4],[3,2]],表示木块的长和宽，当木块的长和宽不大于另个木块的长和宽时，就可以放在上面，
 * 此外数组还可以左右翻转。当长宽都小于等于上一个积木时才可以搭到上一个积木上，此外数组还可以左右翻转。
 * 求最多能搭多少层。（与leetcode354：俄罗斯套娃相似，不过添加了翻转，增加了难度）。
 * 输入：
 * [[5,4], [6,3], [6,7], [6,6], [4,6]]
 * 输出：
 * 4
 */
public class 叠积木 {
    @Test
    public void T_2() {
        /*{5, 8}, {5, 8}, {5, 8}, {5, 8}*/
        int[][] nums = {{5, 4}, {6, 3}, {6, 7}, {6, 6}, {4, 6}, {5, 8},  {5, 8}, {5, 8},  {5, 8}};
        // int[][] nums = {{5, 4}, {6, 3}, {6, 7}, {6, 6}, {4, 6}};
        // System.out.println(solution2(nums));
        System.out.println(solution2_review(nums));
    }

    /*借助俄罗斯套娃解决
    0.将数组整理为x < y
    * 1.按x进行升序排列
    * 2.x相等时按照y进行升序
    * 3.求解y的最长递增(可以相等)子序列*/

    private static int solution2_review(int[][] nums) {
        for (int[] num : nums) {
            if (num[0] > num[1]) {
                num[0] = num[0] ^ num[1];
                num[1] = num[0] ^ num[1];
                num[0] = num[0] ^ num[1];
            }
        }
        Arrays.sort(nums, (o1, o2) -> {
            if(o1[0] == o2[0]){
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });

        int []dp = new int[nums.length];
        Arrays.fill(dp,1);
        int max = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if(nums[i][1] >= nums[j][1]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }
    private static int solution2(int[][] nums) {
        for (int[] num : nums) {
            if (num[0] > num[1]) {
                num[0] = num[0] ^ num[1];
                num[1] = num[0] ^ num[1];
                num[0] = num[0] ^ num[1];
            }
        }
        Arrays.sort(nums, (o1, o2) -> {
            if(o1[0] == o2[0]){
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });

        int []dp = new int[nums.length+1];
        dp[1] = nums[0][1];
        int maxL = 1,maxPos = 0;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i][1] >= dp[maxL]){
                maxPos = i;
                dp[++maxL] = nums[i][1];
            }else {
                /*在递增数组dp中查找大于 当前y 的最小值*/
                int pos = binarySearch(dp,maxL,nums[i][1]);
                dp[pos] = nums[i][1];
                if(pos == maxL){
                    maxPos = i;
                }
            }
        }
        /*输出所有的序列*/
        int [][] serial = getSerial(maxPos,maxL,nums,dp);

        return maxL;
    }

    private static int[][] getSerial(int maxPos,int maxL, int[][] nums, int[] dp) {
        int []res = new int[maxL];
        ArrayList<Integer> gt = new ArrayList<>();
        int maxPoscopy = maxPos-1;
        while (maxPoscopy >= 0 && nums[maxPoscopy][1] >= nums[maxPos][1]){
            gt.add(nums[maxPoscopy--][1]);
        }
        int lastNum = dp[maxL],index = maxL-1;
        for (int i = maxPos-1; i >= 0 && index >= 0; i--) {
            if(nums[i][1] <= lastNum){
                res[--index] = nums[i][1];
                lastNum = nums[i][1];
            }
        }
        int size = gt.size();
        int [][] serial = new int[1+size][maxL];
        for (int i = 0; i < size; i++) {
            int[] temp = Arrays.copyOf(res, res.length);
            temp[res.length-1] = gt.get(i);
            serial[i] = temp;
        }
        res[res.length-1] = dp[maxL];
        serial[size] = res;
        return serial;
    }

    private static int binarySearch(int[] dp, int maxL, int target) {
        int l = 1,r =maxL;
        while (l <= r){
            int mid = l + ((r-l) >>1);
            if(dp[mid] <= target){
                l = mid+1;
            }else {
                r = mid-1;
            }
        }
        return l;
    }

    @Test
    public void T_0() {
        int[][] nums = {{5, 4}, {6, 3}, {6, 7}, {6, 6}, {4, 6}, {5, 8}, {5, 8}, {5, 8}, {5, 8}, {5, 8}};
        System.out.println(solution(nums));
    }


    /*1.自己思考的转化为二维数组解决办法*/
    private static int solution(int[][] nums) {
        int res = 0;
        List<List<int[]>> jm = new ArrayList<>();
        List<HashSet<String>> setList = new ArrayList<>();
        List<int[]> list = new ArrayList<>();
        HashSet<String> set = new HashSet<>();
        if (nums[0][0] > nums[0][1]) {
            int[] n = {nums[0][1], nums[0][0]};
            set.add(nums[0][1] + "-" + nums[0][0]);
            list.add(n);

        } else {
            list.add(nums[0]);
            set.add(nums[0][0] + "-" + nums[0][1]);
        }
        jm.add(list);
        setList.add(set);
        res++;
        for (int i = 1; i < nums.length; i++) {
            int x = Math.min(nums[i][0], nums[i][1]);
            int y = Math.max(nums[i][0], nums[i][1]);
            res = addJm(jm, setList, x, y, res);
        }
        return res;
    }

    private static int addJm(List<List<int[]>> jm, List<HashSet<String>> setList, int x, int y, int res) {

        boolean add = false;
        /*进行剪枝操作*/
        int index = 0;
        for (HashSet<String> set : setList) {
            if (set.contains(x + "-" + y)) {
                add = true;
                int[] t = {x, y};
                for (int i = 0; i < jm.get(index).size(); i++) {
                    List<int[]> list = jm.get(index);
                    if ((jm.get(index).get(i)[0] + "-" + jm.get(index).get(i)[1]).equals(x + "-" + y)) {
                        list.add(i, t);
                        res = Math.max(res, list.size());
                        break;
                    }
                }
                res = Math.max(res, jm.get(index).size());
            }
            index++;
        }

        if (add) {
            return res;
        }

        int size = jm.size();
        for (int i = 0; i < size; i++) {

            HashSet<String> set = setList.get(i);
            List<int[]> list = jm.get(i);

            int pos = 0;
            for (int j = 0; j < list.size(); j++) {

                /*可以叠*/
                if (x >= list.get(j)[0] && y >= list.get(j)[1]) {
                    if (j > 0 && (x > list.get(j - 1)[0] || y > list.get(j - 1)[1])) {
                        /*从中间分出一叠不能叠就另起一堆叠*/
                        add = true;
                        List<int[]> t = new ArrayList<>();
                        int[] n = {x, y};
                        t.add(n);

                        HashSet<String> tset = new HashSet<>();
                        tset.add(x + "-" + y);
                        for (int k = j; k < list.size(); k++) {
                            t.add(list.get(k));
                            tset.add(list.get(k)[0] + "-" + list.get(k)[1]);
                        }
                        jm.add(t);
                        setList.add(tset);
                        break;
                    }
                    int[] t = {x, y};
                    list.add(j, t);
                    add = true;
                    res = Math.max(res, list.size());
                    set.add(x + "-" + y);
                    break;
                }
                if (x < list.get(j)[0] && y < list.get(j)[1]) {
                    pos++;
                }
            }

            if (!add) {
                /*不能叠就另起一堆叠*/
                List<int[]> t = new ArrayList<>();
                HashSet<String> tset = new HashSet<>();
                for (int j = 0; j < pos; j++) {
                    t.add(list.get(j));
                    tset.add(list.get(j)[0] + "-" + list.get(j)[1]);
                }

                tset.add(x + "-" + y);
                setList.add(tset);

                int[] n = {x, y};
                t.add(n);
                jm.add(t);
            }
        }
        return res;
    }
}
